import heapq

## 计算最短路径（使用heap）
def findAllShortestPath(n: int, edges: list[list[int]], src: int) -> int:
    # 定义顶点的访问状态：
    RED, GREEN, WHITE = 2, 1, 0

    # 边权集转邻接表，提高邻接点搜索时的效率
    linkTable = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        linkTable[u].append((v, w))

    # dist[x]: 保存起点到 x 的最短路径长度
    INF = sum(e[2] for e in edges) + 1
    dist = [INF] * (n + 1) 

    # visit[x]表示 x 的访问状态：
    visit = [WHITE] * (n + 1)

    # 初始时只有起点被访问到，设置路径长度为0
    visit[src] = visit[0] = GREEN
    dist[src] = 0

    # 创建分支限界法的关键数据结构: heap
    hp = [(0, src)]

    # 执行dijkstra搜索最短路径
    while hp:
        # 从优先队列中取出下一个路径最短顶点
        _, s = heapq.heappop(hp)

        # 过滤掉已经处理过的顶点
        if visit[s] == RED: continue
        
        # 标记 s 为当前顶点，设置访问状态为红色并开始搜索
        visit[s] = RED

        # 枚举当前顶点 s 的邻接路径，发现新的路径并更新维护排序数组
        for t, w in linkTable[s]:
            # 当前边是 s 的邻边，且目标顶点未完成搜索（不是红色）
            if visit[t] != RED:
                # 计算从起点经过s到达v的路径长度
                d = dist[s] + w
                # 计算出一条更短的路径长度，更新路径长度及访问状态
                if d < dist[t]:
                    dist[t] = d
                    visit[t] = GREEN
                    # 加入堆
                    heapq.heappush(hp, (d, t))

    # 输出结果并返回
    print('所有的顶点路径信息:')
    for i, d in enumerate(dist):
        if visit[i] != RED: continue
        print('目标顶点', i, '->', d)
    return max(dist[1:])

# main
n, src = 5, 1
edges = [[1,2,2],[1,5,8],[1,4,3],[2,3,5],[3,5,1],[4,3,2],[4,5,6]]
ans = findAllShortestPath(n, edges, src)
print('搜索完毕，最远顶点路径为:', ans)
